package _interview75;

import java.util.Arrays;

/**
 * 1137. 第 N 个泰波那契数
 */
public class No1137 {
    private int[] cache;

    public int tribonacci(int n) {
        cache = new int[n + 1];
        Arrays.fill(cache, -1);
        return dfs(n);
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        else if (cache[i] != -1) return cache[i];
        else if (i == 1 || i == 2) return cache[i] = 1;
        else return cache[i] = dfs(i - 1) + dfs(i - 2) + dfs(i - 3);
    }
}
